#include <bits/stdc++.h>

using namespace std;

class Solution {
   public:
    bool dfs(string& s, int pos, int sum, int targt) {
        if (pos == s.size()) {
            return sum == targt;
        }
        int tmp = 0;
        for (int i = pos; i < s.size(); i++) {
            tmp = tmp * 10 + s[i] - '0';
            if (sum + tmp > targt) {
                break;
            }
            if (dfs(s, i + 1, sum + tmp, targt)) {
                return true;
            }
        }
        return false;
    }
    int punishmentNumber(int n) {
        int ret = 0;
        for (int i = 1; i <= n; i++) {
            auto s = to_string(i * i);
            if (dfs(s, 0, 0, i)) {
                ret += i * i;
            }
        }

        return ret;
    }
};